The present invention relates to a highly integrated, high-precision fast Fourier transform (FFT) processor architecture.
The fast Fourier transform class of operations is widely used in communication and sensor signal processing. See for example, Oppenheim, A. V. and R. W. Schafer, 1975, Digital Signal Processing, NJ: Prentice-Hall. Several communication and sensor applications require very high precision (32-bit) real-time Fourier transforms of large (64K-point), complex data blocks. One such application is a high-frequency, spread spectrum communication system such as that described by Perry, B. D., E. A. Palo, R. D. Haggarty, and E. L. Key, 1987, "Trade-off Considerations in the Use of Wideband HF Communications," In Proceedings IEEE International Conference on Communications, Volume 2, pages 0930-0940. Radar systems designed to detect small cross-sectional targets are similarly demanding applications. Although the prior art FFT algorithm is readily implemented with commercial digital signal processing (DSP) components, those components lack either the throughput or precision required for such demanding applications.
There are essentially three prior art approaches available for constructing FFT processors from commercially available integrated circuits. A first approach uses a programmable DSP component such as the TMS320. A second approach uses the commercially available "single-chip" FFT processors and a third approach constructs an FFT processor from available arithmetic components such as multipliers, adders, etc.
Programmable DSP components, such as the TMS320, provide high-precision computation in a very flexible form. Their flexibility and performance have allowed these programmable components to subsume many DSP applications. However, their flexibility comes at the expense of throughput; the DSP chips are not well suited to real-time computation at modest or high throughput rates.
An alternative to programmable DSP components is commercial "single-chip" FFT processors. These components meet the throughput requirements of high performance applications, but they lack the necessary precision. Many such components provide only 16 bits of precision, while a few others offer 24 bits. Further, these "single-chip" processors typically require a large number of supporting components; in particular, address generators and coefficient memories are not incorporated on-chip. Finally, processor throughput and FFT block size are tightly coupled in these processors; larger blocks are typically processed at lower throughput rates.
The third approach is the construction of a high-precision FFT processor from commercially available "building blocks" such as high-performance arithmetic components. This approach provides both precision and performance but the resulting system is large and inflexible. Using this prior art approach, the inventors herein constructed a 32 bit, 16K-point FFT which required nearly 300 components and could not be readily extended to larger block sizes or throughput rates.